The present invention relates to public key cryptography.
It is well known that data can be encrypted by utilising a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted by the public key may only be decrypted by the private key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipients private key.
The most well known and accepted public key cryptosystems are those based on discrete logarithms in finite groups and integer factorization. In particular, the Diffie-Hellman key exchange and the El Gamal protocol in Zp*, p a prime and the RSA system for modulus n=pxc2x7q where p and q are primes have been implemented worldwide. One disadvantage of these systems is that p and n must be relatively large (at least 512 bits) to attain an adequate level of security.
To implement the public key schemes it is necessary to transfer the public key of a recipient to the sender or for the sender to store the keys of all possible recipients. For this reason researchers have looked for public key schemes which reduce the size of the public key. An attractive and promising system is the Diffie-Hellman and El Gamal protocols defined in the group associated with the points on an elliptic curve over a finite field. It appears that a 155-bit elliptic curve scheme gives comparable security to a 1024-bit RSA modulus. Nevertheless, RSA remains a very viable and practical encryption and signing process.
The implementation of RSA system requires a modulus n to be generated from two primes, p,q. The primes p,q, are also used to select a pair of integers, d,e, that are related such that the product e.dxe2x89xa11 (mod(pxe2x88x921)(qxe2x88x921) and that the GCD (greatest common denominator) of e, pxe2x88x921 and qxe2x88x921=1.
The integers e together with the modulus n is used as the public key and the integer d with the modulus n is used as the private key. To encrypt a message the sender uses the public key e,n of the recipient and exponentiates the message M to the integer xe2x80x98exe2x80x99 mod n to generate ciphertext C. The recipient receives the ciphertext C and uses the private key d,n to retrieve the message M by exponentiating C to power d mod n. Therefore the communication between the sender and recipient requires the sender to have access to the public key of the recipient. Typically the public key will be retrieved from the recipient at the start of transmission or it may be stored by the sender. The public key must also be associated with other information such as the recipients identity and be transmitted in a conventional frame format. Accordingly, it is desirable for the data that has to be transmitted to be as short as possible.
On the other hand, the security of the RSA system is determined by the difficulty in factoring the modulus n and this requires p and q to be as large as possible, typically at least 256 bits but preferably 512. n itself will therefore also be large, either 512 or 1024 bits.
It is an object of the present invention to provide a method for reducing the storage and transmission requirement of RSA public moduli without compromising security.
The present invention is based upon the recognition that if the modulus n is an m-bit number it is possible to specify t bits of the number where t is suitably bounded whilst retaining the requisite security. If the t bits can be random bits the criteria for retaining security is somewhat simplified. In one embodiment, a group of users may use the same t random bits and hence only mxe2x88x92t bits need be stored for each user and one copy of the t random bits for the entire group. In another embodiment a user may specify the t bits to be a binary representation of their user ID and other publicly available information. This situation can also be implemented by adjoining a small number of random bits after the information. The applicants have recognised that one can always specify up to m/2 of the bits, but specifying m/2 of the bits comes at the expense of longer key generation (i.e. prime generation). Varied embodiments may be implemented depending on the degrees of dependence between the primes p and q.
According to the present invention, an RSA moduli is generated in which a predetermined set of bits within the moduli have a predetermined configuration.